package string;

/**
 * @Author: 海琳琦
 * @Date: 2022/2/2 22:12
 */
public class RepeatedSubstringPattern {

    public static boolean repeatedSubstringPattern(String s) {
        int maxLength = getNextVal(s);
        System.out.println(maxLength);
        int l = s.length();
        return maxLength != 0 && l % (l - maxLength) == 0;
    }

    private static int getNextVal(String s) {
        int[] nextval = new int[s.length()+2];
        int i = 1, j = 0;
        nextval[1] = 0;
        while (i <= s.length()) {
            if (j == 0 || s.charAt(i - 1) == s.charAt(j - 1)) {
                i++;
                j++;
                nextval[i] = j;
            }else{
                j = nextval[j];
            }
        }
        return nextval[s.length() + 1] - 1;
    }

    public static void main(String[] args) {
        boolean abab = repeatedSubstringPattern("abac");
        System.out.println(abab);
    }
}
